The present application relates to an encoding method, an encoding apparatus, and a program. More particularly, the present application relates to an encoding method, an encoding apparatus, and a program for reducing the size of encoding circuitry while minimizing the amount of operations involved.
In recent years, considerable progress has been made in studies on the field of communication such as mobile communication systems and on the field of broadcasting covering terrestrial and satellite digital broadcasts. That trend has entailed extensive studies on coding theory aimed at improving efficiency in encoding and decoding with error-correcting arrangements.
As the theoretical limit to code performance, the so-called Shannon limit determined by C. E. Shannon's channel coding theorem is well known. Today's studies on coding theory are centered on developing codes with their performance coming close to the Shannon limit. Recently, so-called turbo coding techniques have been developed as codes with their performance approaching the Shannon limit. The turbo coding techniques illustratively include PCCC (Parallel Concatenated Convolutional Codes) and SCCC (Serially Concatenated Convolutional Codes). Apart from these turbo coding techniques, the long-known coding techniques called the Low Density Parity Check Codes (referred to as the LDPC code or codes hereunder) have also come into the limelight.
The LDPC codes were first proposed by R. G. Gallager in “Low Density Parity Check Codes” (by R. G. Gallager, Cambridge, Mass.; M.I.T. Press, 1963). Later, the LDPC codes were highlighted again in particular by D. J. C. MacKay in “Good error correcting codes based on very sparse matrices” (submitted to IEEE Trans. Inf. Theory, IT-45, pp. 399-431, 1999) and by M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi and D. A. Spielman in “Analysis of low density codes and improved designs using irregular graphs” (Proceedings of ACM Symposium on Theory of Computing, pp. 249-258, 1998).
Recent studies have suggested that the LDPC codes, like turbo coding, are capable of approaching the Shannon limit in performance when their code length is increased progressively. Because their minimum distance is proportional to their code length, the LDPC codes provide an excellent block error rate. Another benefit of the LDPC codes is that they manifest few signs of the so-called error floor phenomenon observed with turbo coding and other techniques during decoding.
The following four documents are cited as relevant to the present application:    Y. Kou, S. Lin, M. P. C. Fossorier, “Low-Density Parity-Check Codes Based on Finite Geometries: A Rediscovery and New Results,” IEEE Transactions on Information Theory, Vol. 47, No. 7, pp. 2711-2736, November 2001 (called Non-patent document 1 hereunder).    R. L. Townsend, E. J. Weldon, “Self-Orthogonal Quasi-Cyclic Codes,” IEEE Transactions on Information Theory, Vol. IT-13, No. 2, April 1967 (called Non-patent document 2).    Dieter Roth et al, “SYSTEM FOR BINARY DATA TRANSMISSION,” U.S. Pat. No. 4,453,249, June 1984 (called Patent document 1).    Shin et al, “METHOD OF CONSTRUCTING QC-LDPC CODES USING QTH-ORDER POWER RESIDUE,” US Patent Application Publication, Pub. No. US2005/0149845 A1, July 2005 (called Patent document 2).